#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QueueDataType;
typedef struct QueueNode
{
    QueueDataType data;
    struct QueueNode* next;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QueueDataType x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
QueueDataType QueueFront(Queue* pq);
QueueDataType QueueBack(Queue* pq);


void QueueInit(Queue* pq)
{
    assert(pq);

    pq->head = pq->tail = NULL;
    pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* nex = cur->next;
        free(cur);
        cur = nex;
    }
    pq->head = NULL;
    pq->tail = NULL;
    pq->size = 0;
}



void QueuePush(Queue* pq, QueueDataType x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        return;
    }
    newnode->data = x;
    newnode->next = NULL;

    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = pq->tail->next;
    }
    pq->size++;

}
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }

    pq->size--;
}

bool QueueEmpty(Queue* pq)
{
    assert(pq);

    return pq->size == 0;
}

int QueueSize(Queue* pq)
{
    assert(pq);
    return pq->size;
}

QueueDataType QueueFront(Queue* pq)
{
    assert(pq);
    return pq->head->data;
}

QueueDataType QueueBack(Queue* pq)
{
    assert(pq);
    return pq->tail->data;
}


typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    Queue* empytQ = NULL;
    Queue* notempytQ = NULL;
    if (QueueEmpty(&obj->q1))
    {
        empytQ = &obj->q1;
        notempytQ = &obj->q2;
    }
    else {
        empytQ = &obj->q2;
        notempytQ = &obj->q1;
    }

    QueuePush(notempytQ, x);

}

int myStackPop(MyStack* obj) {
    Queue* empytQ = NULL;
    Queue* notempytQ = NULL;
    if (QueueEmpty(&obj->q1))
    {
        empytQ = &obj->q1;
        notempytQ = &obj->q2;
    }
    else {
        empytQ = &obj->q2;
        notempytQ = &obj->q1;
    }

    while (notempytQ->size != 1)
    {
        int tmp = QueueFront(notempytQ);
        QueuePop(notempytQ);
        QueuePush(empytQ, tmp);
    }

    int re = QueueFront(notempytQ);
    QueuePop(notempytQ);
    return re;

}

int myStackTop(MyStack* obj) {
    Queue* empytQ = NULL;
    Queue* notempytQ = NULL;
    if (QueueEmpty(&obj->q1))
    {
        empytQ = &obj->q1;
        notempytQ = &obj->q2;
    }
    else {
        empytQ = &obj->q2;
        notempytQ = &obj->q1;
    }
    while (notempytQ->size != 1)
    {
        int tmp = QueueFront(notempytQ);
        QueuePop(notempytQ);
        QueuePush(empytQ, tmp);
    }

    int re = QueueFront(notempytQ);
    QueuePop(notempytQ);
    QueuePush(empytQ, re);
    return re;
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}



